package com.yeung.swordoffer;

/**
 * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，
 * 重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
 */
public class 删除链表中的重复节点 {
    public ListNode deleteDuplication(ListNode pHead) {
        //处理临界情况
        if (pHead == null) return null;
        if (pHead.next == null) return pHead;

        ListNode head = new ListNode(-1);//创建一个头节点
        ListNode l_low = head;
        while (pHead != null) {
            ListNode curr = pHead;
            int repeate = 0;
            while (pHead != null && pHead.val == curr.val) {
                //找是否有重复, 有的话重复了几次
                repeate++;
                pHead = pHead.next;
            }
            if (repeate == 1) {
                //没有重复
                l_low.next = curr;
                l_low = l_low.next;
            }//有重复的话就没有给llow赋值,以下一次的llow指针作为头节点(前提是不重复)
        }
        l_low.next = null;
        return head.next;
    }

    /**
     * 重复的几点只保留一个
     *
     * @param pHead
     * @return
     */
    public ListNode deleteDuplication2(ListNode pHead) {
        if (pHead == null) return null;
        ListNode nextNode = deleteDuplication2(pHead.next);
        if (nextNode != null) {
            //当前节点和下一个节点的值重复了, 不要当前节点,而返回下一个节点
            //比如1->2->2->3,  此时下个节点的后续链式2->3 那么下个节点2和当前节点2冲突, 则返回写一个节点
            //1->2->3
            if (pHead.val == nextNode.val) {
                return nextNode;
            } else {
                //把下一个节点链接到当前节点后边
                pHead.next = nextNode;
                return pHead;
            }

        } else return pHead;


    }


}
